#include "../../include/common.h"

/*
    递归实现
*/
void InOrderTraverse_Recursion(BiTree T){
    if (T) {
        InOrderTraverse_Recursion(T->lchild);      //访问该结点的左孩子
        PrintBiT(T);                               //调用操作结点数据的函数方法
        InOrderTraverse_Recursion(T->rchild);      //访问该结点的右孩子
    }
    //如果结点为空，返回上一层
    return;
}

/*********************************************************/
/*
    迭代实现：借助栈
*/
int top = -1;
//定义一个顺序栈
BiTree  a[20];

void Push(BiTree* a,BiTree elem)
{
     a[++top]=elem;
}

void Pop()
{
    if (top==-1) {
        return ;
   }
    top--;
}

BiTree GetTop(BiTree*a){
    return a[top];
}


void InOrderTraverse_Iterative(BiTree Tree)
{
    //临时指针
    BiTree p;
    //根结点进栈
    Push(a, Tree);
     //top!=-1说明栈内不为空，程序继续运行
    while (top!=-1) {
        //一直取栈顶元素，且不能为NULL
        while ((p=GetTop(a)) &&p){
            //将该结点的左孩子进栈，如果没有左孩子，NULL进栈
            Push(a, p->lchild);
        }
        //跳出循环，栈顶元素肯定为NULL，将NULL弹栈。 
        //打印的第一个元素没有右孩子，所以也会Pop掉，再取栈顶元素就是第一个元素的父节点
        Pop();
        if (top!=-1) {
            //取栈顶元素
            p=GetTop(a);
            //栈顶元素弹栈
            Pop();
            //遍历完所有左孩子之后，打印栈顶的元素。
            PrintBiT(p);
            //将p指向的结点的右孩子进栈
            Push(a, p->rchild);
        }
    }
}

void InOrderTraverse_Iterative2(BiTree Tree){
    //定义一个顺序栈
    BiTree a[20];
    //临时指针
    BiTree p;
    p=Tree;
    //当p为NULL且栈为空时，表明树遍历完成
    while (p || top!=-1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            Push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树 弹出时顺便访问右子树
        else{
            p=GetTop(a);
            Pop();
            PrintBiT(p);
            p=p->rchild;
        }
   }
}



void run(char* param[]) {
    if (strcmp(param[1], "middle") != 0)
        return;
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("中序遍历: \n");
    if (strcmp(param[2], "recursion") == 0)
        InOrderTraverse_Recursion(Tree);
    else if (strcmp(param[3], "1"))
        InOrderTraverse_Iterative(Tree);
    else
        InOrderTraverse_Iterative2(Tree);

   printf("\n\n");
}